import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @author VernHe
 * @date 2021年05月20日 15:53
 */
public class Solution_094 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        root.right.left = new TreeNode(3);

        System.out.println(new Solution_094().inorderTraversal(root));
        System.out.println(new Solution_094().inorderTraversal1(root));
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        inorderTraversal(root,res);
        return res;
    }

    private void inorderTraversal(TreeNode root,List<Integer> res) {
            if (root != null) {
                if (root.left != null) {
                    inorderTraversal(root.left,res);
                }
                res.add(root.val);
                if (root.right != null) {
                    inorderTraversal(root.right,res);
                }
            }
            return;
    }

    public List<Integer> inorderTraversal1(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        // 参数判断
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        // 初始化栈
        TreeNode node = root;
        while (node != null) {
            stack.add(node);
            node = node.left;
        }
        while (!stack.isEmpty()) {
            // 把当前节点左边的节点加入到栈中
            TreeNode cur = stack.pop();
            res.add(cur.val);
            if (cur.right != null) {
                stack.add(cur.right);
                // 当加入新节点的时候，将其右边全部加入进来
                while (stack.peek().left != null) {
                    stack.add(stack.peek().left);
                }
            }
        }
        return res;
    }
}
